package practice1_100;

import java.util.Arrays;

public class Practice300 {
    public int lengthOfLIS(int[] nums) {
        int[] table=new int[nums.length];
        Arrays.fill(table,1);
//        table[0]=1;
        dp(nums,0,table);
        int temp=0;
        for (int i=0;i<table.length;i++){
            temp=Math.max(table[i],temp);
        }
        return  temp;
    }
    public void dp(int[] nums,int index,int[] table){
        for (int i=0;i<index;i++){
           if (nums[i]<nums[index]){
               table[index]=Math.max(table[index],table[i]+1);
           }
        }
        if(index==nums.length-1) return;
        dp(nums,index+1,table);
    }

    public static void main(String[] args) {
       int a= new Practice300().lengthOfLIS(new int[]{10,9,2,5,3,7,101,18,35,36,73,2,64,65,2,6,5,75,2,243,57,2,7,5,72,7,47,42,76,6,25,8,69,6,49,45,946,9,469,4,9});
        System.out.println(a);
    }
}
